home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / lzhsourc.lzh / LZH.SRC / LZHSS.C < prev    next >
C/C++ Source or Header  |  1992-07-02  |  9KB  |  287 lines
  1. /* #define protect */
  2.  
  3. /**************************************************************
  4.     LZSS.C -- A Data Compression Program
  5.     (tab = 4 spaces)
  6. ***************************************************************
  7.     4/6/1989 Haruhiko Okumura
  8.     Use, distribute, and modify this program freely.
  9.     Please send me your improved versions.
  10.         PC-VAN        SCIENCE
  11.         NIFTY-Serve    PAF01022
  12.         CompuServe    74050,1022
  13. **************************************************************/
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <ctype.h>
  19.  
  20. /* #define _shell_  */
  21. #define _lzst_
  22. #ifdef _lzst_
  23.   #define from extern
  24. #else
  25.   #define from
  26. #endif
  27.  
  28. #define N         4096    /* size of ring buffer */
  29. #define F           18    /* upper limit for match_length */
  30. #define THRESHOLD    2   /* encode string into position and length
  31.                            if match_length is greater than this */
  32. #define NIL            N    /* index for root of binary search trees */
  33. #define RDERR        13
  34. #define WTERR        14
  35. #define MAXBLK        64
  36.  
  37. extern FILE *infile, *outfile;
  38. extern char *infname, *outfname;
  39. extern unsigned char flg_n;
  40.  
  41. #ifdef _shell_
  42.   extern unsigned long textsize,codesize;
  43. #else
  44. unsigned long     textsize = 0,    /* text size counter */
  45.          codesize = 0;            /* code size counter */
  46. #endif
  47.  
  48. unsigned long int printcount = 0;                   /* counter for reporting progress every 1K bytes */
  49. extern   unsigned char text_buf[N + F - 1];          /* ring buffer of size N, with extra F-1 bytes to facilitate string comparison */
  50. int      match_position, match_length;            /* of longest match.  These are set by the InsertNode() procedure.  */
  51. from int lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children & parents -- These constitute binary search trees. */
  52.  
  53. #ifdef _shell_
  54.  extern FILE    *infile, *outfile;  /* input & output files */
  55. #else
  56.   FILE      *infile, *outfile;  /* input & output files */
  57. #endif
  58.  
  59. #ifdef _shell_
  60. #define setcrc(ch) (crc = (crc >> 8) ^ crctbl [(crc ^ (ch)) & 0xff])
  61. #define setcrcu(ch) (crc_u = (crc_u >> 8) ^ crctbl [(crc_u ^ (ch)) & 0xff])
  62. extern unsigned crc, crc_u, crctbl [];
  63. int crc_getc (register FILE *stream)
  64. {
  65.     register int ch;
  66.  
  67.     if ((ch = getc (stream)) != EOF)
  68.         setcrc (ch);
  69.     return ch;
  70. }
  71.  
  72. int crcu_getc (register FILE *stream)
  73. {
  74.     register int ch;
  75.  
  76.     if ((ch = getc (stream)) != EOF)
  77.         setcrcu (ch);
  78.     return ch;
  79. }
  80.  
  81. void crc_putc (unsigned ch, register FILE *stream)
  82. {
  83.     putc(ch,stream);
  84.     setcrc(ch);
  85. }
  86. #else
  87.   int crc_getc(register FILE *stream)
  88.   {
  89.     return getc(stream);
  90.   }
  91.   void crc_putc(unsigned ch, register FILE *stream)
  92.   {
  93.     putc(ch,stream);
  94.   }
  95. #endif
  96. static void InitOTree(void)  /* initialize trees */
  97. {
  98.     int  i;
  99.  
  100.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  101.        left children of node i.  These nodes need not be initialized.
  102.        Also, dad[i] is the parent of node i.  These are initialized to
  103.        NIL (= N), which stands for 'not used.'
  104.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  105.        for strings that begin with character i.  These are initialized
  106.        to NIL.  Note there are 256 trees. */
  107.  
  108. #ifndef _lzst_
  109.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  110.     for (i = 0; i < N; i++) dad[i] = NIL;
  111. #else
  112.     for (i = N + 1; i <= N + 256; i++) rson[i] = 2*NIL;
  113.     for (i = 0; i < N; i++) dad[i] = 2*NIL;
  114. #endif
  115. }
  116.  
  117. #ifndef _lzst_
  118. static void InsertONode(int r)
  119.     /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  120.        trees (text_buf[r]'th tree) and returns the longest-match position
  121.        and length via the global variables match_position and match_length.
  122.        If match_length = F, then removes the old node in favor of the new
  123.        one, because the old one will be deleted sooner.
  124.        Note r plays double role, as tree node and position in buffer. */
  125. {
  126.     int  i, p, cmp;
  127.     unsigned char  *key;
  128.  
  129.     cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  130.     rson[r] = lson[r] = NIL;  match_length = 0;
  131.     for ( ; ; ) {
  132.         if (cmp >= 0) {
  133.             if (rson[p] != NIL) p = rson[p];
  134.             else {    rson[p] = r;  dad[r] = p;  return;  }
  135.         } else {
  136.             if (lson[p] != NIL) p = lson[p];
  137.             else {    lson[p] = r;  dad[r] = p;  return;  }
  138.         }
  139.         for (i = 1; i < F; i++)
  140.             if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  141.         if (i > match_length) {
  142.             match_position = p;
  143.             if ((match_length = i) >= F)  break;
  144.         }
  145.     }
  146.     dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  147.     dad[lson[p]] = r;  dad[rson[p]] = r;
  148.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  149.     else               lson[dad[p]] = r;
  150.     dad[p] = NIL;  /* remove p */
  151. }
  152.  
  153. static void DeleteONode(int p)    /* deletes node p from tree */
  154. {
  155.     int  q;
  156.  
  157.     if (dad[p] == NIL) return;  /* not in tree */
  158.     if (rson[p] == NIL) q = lson[p];
  159.     else if (lson[p] == NIL) q = rson[p];
  160.     else {
  161.         q = lson[p];
  162.         if (rson[q] != NIL) {
  163.             do {  q = rson[q];  } while (rson[q] != NIL);
  164.             rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  165.             lson[q] = lson[p];  dad[lson[p]] = q;
  166.         }
  167.         rson[q] = rson[p];  dad[rson[p]] = q;
  168.     }
  169.     dad[q] = dad[p];
  170.     if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
  171.     dad[p] = NIL;
  172. }
  173. #else
  174.   void InsertONode(int r);
  175.   void DeleteONode(int p);  /* deletes node p from tree */
  176. #endif
  177.  
  178. void EncodeOld(void)
  179. {
  180.     register int  i, c, len, r, s, last_match_length, code_buf_ptr;
  181.     unsigned char  code_buf[17], mask;
  182. /*      unsigned long done=N; */
  183.     printcount=textsize=0;
  184.     InitOTree();  /* initialize trees */
  185.     code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and
  186.         code_buf[0] works as eight flags, "1" representing that the unit
  187.         is an unencoded letter (1 byte), "0" a position-and-length pair
  188.         (2 bytes).  Thus, eight units require at most 16 bytes of code. */
  189.     code_buf_ptr = mask = 1;
  190.     s = 0;    r = N - F;
  191.     for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with
  192.         any character that will appear often. */
  193.     for (len = 0; len < F && (c = crc_getc(infile)) != EOF; len++)
  194.         text_buf[r + len] = c;    /* Read F bytes into the last F bytes of
  195.             the buffer */
  196.     if ((textsize = len) == 0) return;  /* text of size zero */
  197.     for (i = 1; i <= F; i++) InsertONode(r - i);  /* Insert the F strings,
  198.         each of which begins with one or more 'space' characters.  Note
  199.         the order in which these strings are inserted.    This way,
  200.         degenerate trees will be less likely to occur. */
  201.     InsertONode(r);    /* Finally, insert the whole string just read.    The
  202.         global variables match_length and match_position are set. */
  203.     do {
  204.         if (match_length > len) match_length = len;  /* match_length
  205.             may be spuriously long near the end of text. */
  206.         if (match_length <= THRESHOLD) {
  207.             match_length = 1;  /* Not long enough match.  Send one byte. */
  208. #ifndef protect
  209.             code_buf[0] |= mask;  /* 'send one byte' flag */
  210. #endif
  211.             code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
  212.         } else {
  213. #ifdef protect
  214.             code_buf[0] |= mask;
  215. #endif
  216.             code_buf[code_buf_ptr++] = (unsigned char) match_position;
  217.             code_buf[code_buf_ptr++] = (unsigned char)
  218.                 (((match_position >> 4) & 0xf0)
  219.               | (match_length - (THRESHOLD + 1)));    /* Send position and
  220.                     length pair. Note match_length > THRESHOLD. */
  221.         }
  222.         if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
  223.             for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
  224.                 putc(code_buf[i], outfile);    /* code together */
  225.             codesize += code_buf_ptr;
  226.             code_buf[0] = 0;  code_buf_ptr = mask = 1;
  227.         }
  228.         last_match_length = match_length;
  229.         for (i = 0; i < last_match_length &&
  230.                 (c = crc_getc(infile)) != EOF; i++) {
  231.             DeleteONode(s);        /* Delete old strings and */
  232.             text_buf[s] = c;    /* read new bytes */
  233.             if (s < F - 1) text_buf[s + N] = c;  /* If the position is
  234.                 near the end of buffer, extend the buffer to make
  235.                 string comparison easier. */
  236.             s = (s + 1) & (N - 1);    r = (r + 1) & (N - 1);
  237.                 /* Since this is a ring buffer, increment the position
  238.                    modulo N. */
  239.             InsertONode(r);    /* Register the string in text_buf[r..r+F-1] */
  240.         }
  241.         if ((textsize += i) > printcount) {
  242.             if (!flg_n) putchar('*');  printcount += N;
  243.                 /* Reports progress each time the textsize exceeds
  244.                    multiples of 1024. */
  245.         }
  246.